package com.lzq.leetcode.test;

public class SparseArraySearch {
    // 查找第一个大于等于target的元素索引
    public static int firstGreaterOrEqual(Comparable[] arr, Comparable target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = findNonEmptyMid(arr, left, right);
            if (mid == -1) break; // 区间内全为空

            int cmp = arr[mid].compareTo(target);

            if (cmp >= 0) {
                result = mid; // 记录候选位置
                right = mid - 1; // 继续向左寻找更小的索引
            } else {
                left = mid + 1; // 目标在右侧
            }
        }

        return result;
    }

    // 查找第一个大于target的元素索引
    public static int firstGreater(Comparable[] arr, Comparable target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = findNonEmptyMid(arr, left, right);
            if (mid == -1) break;

            int cmp = arr[mid].compareTo(target);

            if (cmp > 0) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result;
    }

    // 核心：在区间内找到非空中间位置
    private static int findNonEmptyMid(Comparable[] arr, int left, int right) {
        int mid = left + (right - left) / 2;
        int low = mid, high = mid;

        // 向两侧扩展寻找非空元素
        while (low >= left || high <= right) {
            if (low >= left && arr[low] != null) return low;
            if (high <= right && arr[high] != null) return high;
            low--;
            high++;
        }

        return -1; // 区间内全为空
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] {
            1, 2, null, 3, null, null, 4, 5
        };
        System.out.println(firstGreater(arr, 3));
    }
}